<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>Maxmilite</title>
    <link rel="icon" href="../icon.png" type="image/x-icon">
</head>

<link rel="stylesheet" href="../css/style-archive.css">

<canvas id="snow-flake-app"></canvas>
<script src="../js/snow-flake-app.js"></script>

<!-- <ul class="nav">
    <li style="width: 40%;">
        <div>
            <p style="font-size: xx-large;"><img src="../icon.png" height="40px" width="40px"
                    style="border-radius: 4px;">&nbsp;Maxmilite</p>
        </div>
    </li>
</ul> -->

<div class="main">
    <h1 style="text-align: center">
        P7479 【B】至曾是英雄的您 题解
    </h1>
</div>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
</script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<xmp theme="united" style="display:none;" id="section">
本题解思路有别于与其他题解。

### 简化版题意分析

白/黑棋快是由白/黑棋组成的连通块。

给您一副围棋黑棋块盘面，要求填上白棋块让黑棋块周围一格的空位都被填掉。

必须要保证周围一格没有空位白棋块的数量小于等于 $1$。

(这种题意可能会对未接触过围棋的选手~~我~~比较友好)

### 解法

我们先来讲一下总的做法：**找到所有需要填白棋的位置，判断这个位置的白棋块是否满足需求，填上白棋，计数，判断，输出答案。**

既然最终目标是填掉黑棋块周围一格的空位，那么我们首先要找到这一些空位。

这里我调用了一个函数 `checkLiberty`

```cpp
// (liberty 是气的英文单词)
// 使用字符串二维数组 a 记录棋盘，dx、dy 数组即为遍历当前位置周围一格的路径
// int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};
// char a[2005][2005];
// 返回值 0 意为这里不是符合要求的空位，1 意为这里是符合要求的空位

inline int checkLiberty(int i, int j)
{
	if (a[i][j] == '*' || a[i][j] == 'p')
		return 0;
	for (int k(0), nx, ny; k <= 3; ++k)
	{
		nx = i + dx[k];
		ny = j + dy[k];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
			if (a[nx][ny] == '*')
				return 1;
	}
	return 0;
}
```

这里有一句 `a[i][j] == 'p'`，我们暂且一放，这个 `p` 会在下面用到。

我们先来看一下这段函数的作用。

如果当前位置是黑棋子，那么就返回 $0$。如果不是黑棋子，说明这里是空位，我们需要在周围一格找一下有没有黑棋子，如果有，那这个位置就是符合要求的空位。

找到了我们需要的空位，那么我们就要开始往这些空位里填白棋子了。

这里我调用了一个函数 `check`。

```cpp
// vis 数组记录走过的格子
// 返回值 0 意为这里无法按照题目要求放上白棋，1 意为这里可以
// 要求：这一白棋块周围至少有一个空位。

int check(int i, int j)
{
	vis[i][j] = 1;
	for (int k(0), nx, ny; k <= 3; ++k)
	{
		nx = i + dx[k];
		ny = j + dy[k];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0)
		{
			if (a[nx][ny] == '.')
				if (checkLiberty(nx, ny) == 0)
				{
					vis[i][j] = 0;
					return 1;
				}
				else if (check(nx, ny) == 1)
				{
					vis[i][j] = 0;
					return 1;
				}
		}
	}
	vis[i][j] = 0;
	return 0;
}
```

我们先来看一下这段函数的作用。

对于这个位置，我们使用类似 DFS 的技巧，往外扩展搜索能让白棋合法放置的情况。

也就是说让这个位置放上白棋，之后一直往外铺，直到找到合适的空位能够让这个白棋放置成为合法的。

我们注意到这一段代码

```cpp
if (a[nx][ny] == '.')
	if (checkLiberty(nx, ny) == 0)
	{
		vis[i][j] = 0;
		return 1;
	}
	else if (check(nx, ny) == 1)
	{
		vis[i][j] = 0;
		return 1;
	}
```

我们在搜索的时候搜到了空位，但是我们并不知道这个位置是不是黑棋块周围一格的空位（需要被填充的空位），所以我们需要判断。

调用 `checkLiberty` 函数，如果这里不是黑棋块周围一格的空位，那么我们在这个位置放上白棋就是符合的。

否则这里也要放上白棋，那么我们以这个新的白棋为起点，继续搜索。

这样搜索过后，我们就找到了白棋的情况。（周围没有合适的空位/周围有合适的空位）

我用一个 `cur` 变量来记录不符合要求的白棋块的数量，用于最终的结果判断。

找到情况之后，我调用了一个 `extendArea` 函数，用来把白棋填上。

```cpp
inline void extendArea(int i, int j)
{
	a[i][j] = 'p';
	for (int k(0), nx, ny; k <= 3; ++k)
	{
		nx = i + dx[k];
		ny = j + dy[k];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != 'p')
			if (checkLiberty(nx, ny) == 1)
				extendArea(nx, ny);
	}
	return;
}
```

因为这个位置所在的白棋块在 `check` 函数中已经被判定完了，所以我们就要把这个白棋所在的白棋块全部填上。

然后我们的 `p` 就出现了。

> 这里有一句 `a[i][j] == 'p'`，我们暂且一放，这个 `p` 会在下面用到。
>
> ——来自于 `checkLiberty` 函数讲解部分。

我们可以回到这一句了，如果这个位置是一个白棋，那么这个位置肯定不是空位，所以返回为 $0$。

在判断 `cur` 和 $1$ 的关系后，我们就可以输出答案了。

**找到所有需要填白棋的位置，判断这个位置的白棋块是否满足需求，填上白棋，计数，判断，输出答案。**

### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, m, t;
char a[2005][2005];
int vis[2005][2005];
int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};

inline int checkLiberty(int i, int j)
{
	if (a[i][j] == '*' || a[i][j] == 'p')
		return 0;
	for (int k(0), nx, ny; k <= 3; ++k)
	{
		nx = i + dx[k];
		ny = j + dy[k];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
			if (a[nx][ny] == '*')
				return 1;
	}
	return 0;
}

int check(int i, int j)
{
	vis[i][j] = 1;
	for (int k(0), nx, ny; k <= 3; ++k)
	{
		nx = i + dx[k];
		ny = j + dy[k];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0)
		{
			if (a[nx][ny] == '.')
				if (checkLiberty(nx, ny) == 0)
				{
					vis[i][j] = 0;
					return 1;
				}
				else if (check(nx, ny) == 1)
				{
					vis[i][j] = 0;
					return 1;
				}
		}
	}
	vis[i][j] = 0;
	return 0;
}

inline void extendArea(int i, int j)
{
	a[i][j] = 'p';
	for (int k(0), nx, ny; k <= 3; ++k)
	{
		nx = i + dx[k];
		ny = j + dy[k];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != 'p')
			if (checkLiberty(nx, ny) == 1)
				extendArea(nx, ny);
	}
	return;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		for (int i(1); i <= n; ++i)
			cin >> (a[i] + 1);
		int cur = 0;
		for (int i(1); i <= n; ++i)
			for (int j(1); j <= m; ++j)
				if (checkLiberty(i, j))
				{
					if (check(i, j) == 0)
						++cur;
					extendArea(i, j);
				}
					
		if (cur <= 1)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
	return 0;
}
```
</xmp>


<script src="strapdown/v/0.2/strapdown.js"></script>

<div>
    <!-- Button Here -->
    <!-- Fixed Button 2021-04-18-->
    <a class="button" href="../archives.html" style="width: 40%; border-radius: 8px; margin-left: 30%; margin-top: 100px;  margin-bottom: 40px">
        <p style="font-size: 2vmax;">
            <<< Return to archive list </p>
    </a>
</div>

</html>